package Lee_code;

import java.util.*;

public class Lee_752 {

    public int openLock(String[] deadends, String target) {

        HashSet<String> dead = new HashSet<>();
        HashSet<String> seen = new HashSet<>();
        Collections.addAll(dead, deadends);
        Deque<String> deque = new ArrayDeque<>();
        deque.offer("0000");

        //记录移动次数
        int step=0;
        while (!deque.isEmpty())
        {
            step++;
            int len = deque.size();
            for(int i=0; i<len; i++)
            {
                String now = deque.poll();
                if(now.equals(target))
                {
                    return step;
                }
                if(!seen.contains(now)&&!dead.contains(now))
                {
                    for(String str: get_next(now))
                    {
                        deque.offer(str);
                    }
                    seen.add(now);
                }
            }
        }
        return -1;
    }

    public List<String> get_next(String now)
    {
        List<String> res = new LinkedList<>();
        for(int i=0; i<4; i++)
        {
            char[] char_now = now.toCharArray();
            char temp = char_now[i];
            char temp_up = next_add(temp);
            char temp_down = next_min(temp);

            char_now[i] = temp_up;
            res.add(Arrays.toString(char_now));

            char_now[i] = temp_down;
            res.add(Arrays.toString(char_now));
        }
        return res;
    }

    public char next_add(char in)
    {
        if(in=='9')
            return '0';
        else
            return (char)(in+1);
    }
    public char next_min(char in)
    {
        if(in=='9')
            return '0';
        else
            return (char)(in+1);
    }
}
